/*
 * 1016. 带重复元素的排列
 * 给定一个数字列表，返回其所有可能的排列。
 * https://www.lintcode.com/zh-cn/problem/permutations-ii/
 * 
 * 样例
 * 给出一个列表[1,2,2]，其全排列为：
 * [
 *   [1,2,2],
 *   [2,1,2],
 *   [2,2,1]
 * ]
 * 
 * 挑战
 * 使用递归和非递归分别解决。
 * 
 * 参考算法：
 * https://blog.csdn.net/summerxiachen/article/details/60579623
 * 
 * 2018.06.07 @jeyming
 */
package permutations_ii_1016;

import java.util.ArrayList;
import java.util.List;

public class Permutations_ii_1016 {

	 /*
     * @param nums: A list of integers.
     * @return: A list of permutations.
     */
	static List<List<Integer>> result = new ArrayList<List<Integer>>();
	
	static void swap(int x, int y, int[] nums) {
		int tmp = nums[ x ];
		nums[ x ] = nums[ y ];
		nums[ y ] = tmp; 
	}
	
	static void resove(int[] nums, int n) {
		if( n == nums.length ) {
			List<Integer> list = new ArrayList<>();
			for(int i = 0; i<nums.length; ++i)
				list.add(nums[i]);
			for(int i = 0; i < result.size(); ++i) {
				if( list.equals( result.get(i) ))
					return;
			}
			result.add(list);
			return;
		}
		for(int i = n; i < nums.length; ++i) {
			swap(n,i,nums);
			resove( nums,n+1 );
			swap(n,i,nums);
		}
	}
	
    public static List<List<Integer>> permute(int[] nums) {
        // write your code here
    	
//    	int cnt = 1;
//    	for(int i = nums.length; i  > 0; --i) {
//    		cnt*=i;
//    	}
//    	for(int i = 0; i < cnt; ++i) {
//    		for(int j = 0; j < nums.length; ++j) {
//    			List<Integer> list = new ArrayList<Integer>();
//    			list.add( nums[( j + nums.length )%nums.length] );
//    			for(int z = j + 1, a = 0; a < nums.length-1; ++z, ++a) {
//    				list.add( nums[ ( j + z + nums.length )% nums.length]);
//    			}
//    			result.add(list);
//    		}
//    		
//    	}
    	resove(nums,0);
    	for(int i = 0; i < result.size(); ++i) {
    		System.out.println(result.get(i));
    	}
		return result;
    }
    
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int num[] = {1,2,2};
		permute(num);
	}

}
